/**
 * 76. 最小覆盖子串
 */
class Solution1 {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray(), t = tt.toCharArray();
        int[] hashS = new int[128], hashT = new int[128]; // 大小写字母一共有52个
        int count = 0, len = t.length, min = Integer.MAX_VALUE;

        int[] ret = new int[2];
        ret[0] = ret[1] = -1;

        // 把t存在的字母都存进hash表里
        for(int i = 0; i < t.length; i++) {
            hashT[t[i]]++;
        }

        for(int left = 0, right = 0; right < s.length; right++) {
            // 进窗口
            hashS[s[right]]++;

            // 维护有效字符个数count
            if(hashS[s[right]] <= hashT[s[right]]) count++;

            while(count == len) {
                int n = right - left + 1; // 当前长度
                // 记录当前的左右下标，并更细min
                if(n < min) {
                    ret[0] =left;
                    ret[1] = right;
                    min = n;
                }

                // 出窗口
                if(hashS[s[left]] <= hashT[s[left]]) count--; // 维护有效字符个数count
                hashS[s[left]]--;
                left++;
            }
        }
        if(ret[0] == -1) return "";
        return new String(ss.substring(ret[0], ret[1] + 1));
    }
}